#include <vector>
#include <queue>

using namespace std;

// 并行课程 III
// 给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n
// 同时给你一个二维整数数组 relations ，
// 其中 relations[j] = [prevCoursej, nextCoursej]
// 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）
// 同时给你一个下标从 0 开始的整数数组 time
// 其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。
// 请你根据以下规则算出完成所有课程所需要的 最少 月份数：
// 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
// 你可以 同时 上 任意门课程 。请你返回完成所有课程所需要的 最少 月份数。
// 注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）
// 测试链接 : https://leetcode.cn/problems/parallel-courses-iii/

class Solution 
{
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) 
    {
        vector<vector<int>> g(n);
        vector<int> indegree(n);
        for(auto& r : relations)
        {
            int x = r[0] - 1, y = r[1] - 1;
            g[x].push_back(y);
            ++indegree[y];
        }

        queue<int> q;
        vector<int> cost(n);
        for(int i = 0; i < n; ++i)
        {
            if(!indegree[i]) q.push(i);
        }

        int ret = -1;
        while(!q.empty())
        {
            int x = q.front();
            q.pop();
            cost[x] += time[x];
            ret = max(ret, cost[x]);
            for(int y : g[x])
            {
                cost[y] = max(cost[y], cost[x]);
                if(--indegree[y] == 0) q.push(y);
            }
        }
        return ret;
    }
};